611. Valid Triangle Number

1. Question

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

2. Examples

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

2.1. Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

3. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-triangle-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

4. Solutions

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        if (null == nums || nums.length < 3) {
            return 0;
        }

        int res = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {

                // 暴力算法
//                for (int k = j + 1; k < nums.length; k++) {
//                    if (nums[i] + nums[j] > nums[k]){
//                        res++;
//                    }
//                }

                // 二分法
                int left = j + 1;
                int right = nums.length - 1;
                int k = j;

                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                res += k - j;
            }
        }

        return res;
    }
}

public class Solutions {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int cnt = 0;
        int n = nums.length;

        for (int i = n - 1; i > 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    cnt += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return cnt;
    }
}